Recently, regulations to protect personal information and secret information are tightened, on the other hand, markets of services that utilizes such information are expanding. Then, attention is paid to masking (or hiding) techniques that are capable of utilizing data with the personal information and secret information protected. There is a technique that uses a cryptographic technique or statistical technique, depending on data types and/or service requirement, among the masking techniques.
As a masking technique that uses the cryptographic technique, a homomorphic encryption technique is known. The homomorphic encryption technique is a public-key cryptographic method in which a key for encryption and a key for decryption are different, and has a function for enabling data operation with data encrypted. For example, as for texts m1 and m2, E represents an encryption function in the homomorphic encryption method for addition or multiplication. Then, there is a property represented by a following expression (1) or (2).E(m1)+E(m2)=E(m1+m2)  (1)E(m1)*E(m2)=E(m1*m2)  (2)
The encryption method that has the property of the expression (1) is called “homomorphic with respect to addition”, and the encryption method that has the property of the expression (2) is called “homomorphic with respect to multiplication”.
When the homomorphic encryption method is used, it is possible to obtain an encrypted text that is a calculation result of the addition or multiplication by adding or multiplying encrypted texts without decrypting the encrypted texts. This property of the homomorphic encryption method is expected to be used in a field such as an electronic voting system and electronic money, furthermore recently in a cloud-computing field.
As the homomorphic encryption method, Rivest Shamir Adleman (RSA) encryption method (which is homomorphic only with respect to the multiplication) and Additive ElGamal encryption method (which is homomorphic only with respect to the addition) are typical. Moreover, a homomorphic encryption method (i.e. the expressions (1) and (2) are established.) that is capable of adding and multiplying was proposed in 2009 (See C. Gentry, “Fully Homomorphic encryption using ideal lattices”, STOC 2009, ACM, pp. 169-178, 2009.). However, this homomorphic encryption method is known to be impractical in view of the processing capability and size of encrypted data. Then, in 2011, a homomorphic encryption method, which is capable of adding and multiplying and practical in view of both of the processing capability and size of the encrypted data, was proposed, and its application example is presented (See K. Lauter, M. Naehrig and V. Vaikuntanathan, “Can Homomorphic Encryption be Practical?”, In ACM workshop on Cloud Computing Security Workshop-CCSW 2011, ACM, pp. 113-124, 2011.).
Here, the homomorphic encryption method proposed in 2011 will be explained (See Section 3.2 of the aforementioned paper). Firstly, in order to generate cryptographic keys, three key generation parameters (n, q, t) are prepared, mainly. “n” is an integer that is a power of “2” and called “a lattice degree”, q is a prime number, and t is an integer that is less than the prime number q. As for the procedure of the cryptographic key generation, a polynomial sk whose coefficient is respectively very little and that has degree n is randomly generated as a secret key, firstly. The value of each coefficient is limited by a certain parameter σ. Next, a polynomial a1 that has degree n and whose coefficient is respectively less than q and a polynomial e that has degree n and whose coefficient is respectively very little, are randomly generated.
Then, a0=−(a1*sk+t*e) is calculated, and a pair (a0, a1) is defined as a public key pk. However, a polynomial whose degree is less than the degree n is always calculated by using xn=−1, xn+1=−x, . . . with respect to polynomials whose degree is greater than the degree n when the polynomial calculation is performed for “a0”. Furthermore, as for coefficients of the polynomial, a remainder obtained by dividing by the prime number q is outputted. The space in which such operations are performed is often represented as Rq=Fq[x]/(xn+1) scholarly.
Next, 3 polynomials u, f and g that have the degree n and whose coefficient is respectively very little are randomly generated for the public key pk=(a0, a1) and text data m that is represented by a polynomial of degree n and whose coefficient is respectively less than t, and encrypted data E(m, pk)=(c0, c1) of the text data m is defined as follows:c0=a0*u+t*g+m,c1=a1*u+t*f 
This calculation is also performed on the space Rq.
Then, as for two encrypted texts E (m1, pk)=(c0, c1) and E (m2, pk)=d0, d1), the cryptographic addition E (m1, pk)+E(m2, pk) is calculated as (c0+d0, c1+d1), and the cryptographic multiplication E (m1, pk)*E(m2, pk) is calculated as (c0+d0, c0*d1+c1*d0, c1*d1). Note that the number of components in the vector of the encrypted text is changed from “2” to “3” when performing the cryptographic multiplication.
Finally, in the decryption processing, an encrypted text c=(c0, c1, c2, . . . ) is decrypted by using the secret key sk by calculating D (c, sk)=[c0+c1*sk+c2*sk2+ . . . ] q mod t. Here, it is assumed that the number of components of the encrypted text data has been increased by cryptographic operations such as cryptographic multiplication for plural times. Here, as a value [z] q, a remainder w is calculated by dividing the integer z by q, and in case of w<q, [z]q=w is outputted, and in case of w≧q, [z]q=w−q is outputted. Furthermore, a mod t means a remainder obtained by dividing the integer a by t.
In order to make it easy to understand the aforementioned calculations, numerical examples will be exhibited.    Secret key sk=Mod(Mod(4, 1033)*x3+Mod(4, 1033)*x2+Mod(1, 1033)*x, x4+1)    Public key pk=(a0, a1)    a0=Mod(Mod(885, 1033)*x3+Mod(519, 1033)*x2+Mod(621, 1033)*x+Mod(327, 1033), x4, x4+1)    a1=Mod(Mod(661, 1033)*x3+Mod(625, 1033)*x2+Mod(861, 1033)*x+Mod(311, 1033), x4+1)    E(m, pk)=(c0, c1)    Text data m=3+2x+2x2+2x3     c0=Mod(Mod(822, 1033)*x3+Mod(1016, 1033)*x2+Mod(292, 1033)*x+Mod(243, 1033), x4+1)    c1=Mod(Mod(840, 1033)*x3+Mod(275, 1033)*+Mod(628, 1033)*x+Mod(911, 1033), x4+1)
As for the aforementioned values, (4, 1033, 20) is used as the key generation parameters (n, q, t). Furthermore, Mod (a, q) means a remainder obtained by dividing the integer a by the prime number q, and Mod (f (x), x4+1) means a remainder polynomial obtained by dividing the polynomial f (x) by the polynomial x4+1. However, note x4=−1, x5=x, . . . .
Next, the pattern matching will be explained, simply. The pattern matching is a processing to determine whether or not a pattern character string exists in a text character string, for example, and specifically, a processing to determine whether or not a pattern character string P=“abbac” exists in a text character string T=“acbabbaccb” is considered. In such a case, as illustrated in FIG. 1, while the pattern character string P is shifted character-by-character against the text character string T, the number of characters at which the text and the pattern coincide (also called distance) is calculated. In FIG. 1, an arrangement of values that represent the aforementioned number of characters is called “a score vector”. In this example, because the length of the pattern character string P is “5”, it is understood that the pattern character string P and the text character string T coincide at a component position whose value is “5” in the score vector.
Thus, in the pattern matching without the encryption, the distance with the text character string is calculated while shifting the pattern character string P character-by-character against the text character string T.
On the other hand, in the secure pattern matching that utilizes the homomorphic encryption method, plural distances are calculated in a state where the text character string T and pattern character string P are encrypted in the homomorphic encryption method. Here, a secure pattern matching calculation model is considered in which there are an information registrant who has a text character string T, a collator who has a pattern character string P and a cloud provider who performs a cryptographic distance calculation in the secure pattern matching. Firstly, the collator generates a public key and secret key by generating keys in the homomorphic encryption method, and opens only the public key in public for the information registrant and the cloud provider. After that, the information registrant uses the public key transmitted from the collator to encrypt the text character string T, which is owned by itself, in the homomorphic encryption method, and saves the encrypted text E (T) in a database in the cloud. In order to determine whether the pattern character string P exists, the collator encrypts the pattern character string P in the homomorphic encryption method, and sends the encrypted pattern E (P) to the cloud. The cloud calculates plural distances for T and P with respect to the encrypted text E (T) and encrypted pattern E (P) while the encrypted state is kept, and transmits the calculation results to the collator. The collator decrypts encrypted calculation results transmitted from the cloud by using the secret key which is owned by itself, and determines whether or not the pattern character string P is included in the text character string T from the decryption results.
In case of such secure pattern matching in the cloud, because a processing is performed in a state where data is encrypted on the cloud, data of the information registrant and the collator is not opened in public. Accordingly, in an environment such as cloud whose security is not so strong, it is possible to outsource the pattern matching processing.
However, only application of the homomorphic encryption method simply to the pattern matching is impractical in view of data amounts and/or calculation loads.
Non-Patent Document 1: C. Gentry, “Fully Homomorphic encryption using ideal lattices”, STOC 2009, ACM, pp. 169-178, 2009.
Non-Patent Document 2: K. Lauter, M. Naehrig and V. Vaikuntanathan, “Can Homomorphic Encryption be Practical?”, In ACM workshop on Cloud Computing Security Workshop-CCSW 2011, ACM, pp. 113-124, 2011.